
% Created 2011-10-27 do 16:51
\documentclass[a4paper, 12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{soul}
\usepackage{textcomp}
%\usepackage{marvosym}
%\usepackage{wasysym}
%\usepackage{latexsym}
%\usepackage{amssymb}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{placeins}
\usepackage{pict2e}
\usepackage{subfig}
\usepackage{color}
\usepackage{multirow}
\usepackage{cite}
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
%\usepackage{cmbright}
\usepackage[english]{babel}
\usepackage[a4paper,margin=2.5cm]{geometry}
 \hyphenpenalty=5000
\tolerance=1000
\providecommand{\alert}[1]{\textbf{#1}}
\newfloat{MATLAB code}{h}{}
\usepackage{tikz,pgfplots}
\setlength\parindent{0pt}


\pgfplotsset{compat=newest}
\pgfplotsset{plot coordinates/math parser=false}

\newtheorem{mydef}{THEOREM}

\title{Beschrijving Algoritmes}
\author{Roel Matthysen - \today}
\date{}

\newlength\figureheight
\newlength\figurewidth
\setlength\figureheight{2cm}
\setlength\figurewidth{12cm}


\begin{document}
\newcommand{\comm}[1]{\textcolor{RubineRed}{\newline#1\newline}}

\maketitle
The concept of optimal coefficients was introduced in [1], and their significance for the approximate computation of multidimensional integrals of arbitrary multiplicity $s$ was indicated. Various algorithms for computing $s$-dimensional optimal coefficients modulo $p$ where $p$ is he number of nodes of the quadrature formula were obtained in [1]-[3]. The realization of these algorithms required the execution of $O(p^2)$ or $O(p^{1+1/3})$ elementary arithmetic operations.

In this note we present more economical algorithms for $p=2^n$ whose realization requires the execution of $O(p)$ or $O(p\ln{p})$ operations.

Let $n$ and $s$ be positive integers, and $x_1,...,x_s$ odd integers. Summations over odd integers $m$ is indicated by $\sum_m^*$. For $v=1,...,n$ we define the function $h_v(x_1,x_2,...,x_s)$ by
 \begin{equation*}
h_v(x_1,x_2,...,x_s)=\frac{1}{2^v}\sum_{m=1}^{2^v}{}^*\left(2n-2v+\frac{1}{||mx_1/2^v||}\right)\cdots\left(2n-2v+\frac{1}{||mx_s/2^v||}\right)
\end{equation*}
where $||mx_j/2^v||$ is the distance from $mx_j/2^v$ to the nearest integer. 

Take $a_{11}=...=a_{s1}=1$. Suppose that $v\ge2$ and that the odd integers $a_{1v-1},...,a_{sv-1}$ are known for $2\le v \le n$ we define $a_{1v},...,a_{sv}$ by the equalities
\begin{equation*}
a_{1v}=a_{1v-1}+2^{v-1}z_1',...,a_{sv}=a_{sv-1}+2^{v-1}z_s'
\end{equation*} 
where $z_1',...z_s'$ are the variables at which the function
\begin{equation*}
h_v(a_{1v-1}+2^{v-1}z_1',...,a_{sv-1}+2^{v-1}z_s')
\end{equation*}
attains a minimum as the variables $z_1,...,z_s$ run through the values 0 and 1 independently.
\begin{mydef}
For an arbitrary positive integer n the integer $a_1,...,a_s$ defined by the equalities $a_1=a_{1n},...,a_s=a_{sn}$ are optimal coeffecients modulo $p=2^n$.
\end{mydef}
\begin{proof}
For $v=1,...,n$ we introduce the notation
\begin{align*}
h_v &=h_v(a_{1v},a_{2v},...,a_{sv}). \\
H_v &= \sum_{k=1}^{v-1} \sum_{m=1}^{2^k} {}^*\frac{1}{||ma_{1k}/2^k|| \cdots ||ma_{sk}/2^k||}+(2^{n+1}-2^v)h_v.
\end{align*}
\comm{De notatie $h_v$ duidt rekening houdend met de definities hierboven op de waarde van het minimum van $h_v(a_{1v-1}+2^{v-1}z_1',...,a_{sv-1}+2^{v-1}z_s')$
}
\clearpage
Observing that if $v \ge 2$, then
\begin{equation}
\label{hvinequality}
\frac{1}{2}\sum_{z=0}^{1}\frac{1}{||m(a+2^{v-1}z)/2^v||}\le2+\frac{1}{||ma/2^{v-1}||}
\end{equation}
\comm{
Dit is logisch omdat de maximale waarde van $1/||x||$ gelijk is aan 2. De maximale waarde van de som aan de linkerkant is dus gelijk aan 2, kleiner dan het rechterlid.}
for odd $a$ and $m$, we get
\begin{equation}
\label{eqn:vlev-1}
\begin{aligned}
&h_v \le \frac{1}{2^s} \sum^1_{z_1,...z_s = 0} h_v(a_{1v-1}+2^{v-1}z_1,...,a_{sv-1}+2^{v-1}z_s) \\
&\mbox{\comm{$h_v$ is de waarde van het minimum, en is dus kleiner of gelijk aan de gemiddelde waarde van $h_v$.}} \\
&\mbox{\comm{De som in het rechterlid kan dan opgesplitst worden in $\sum_{z_1,...,z_s=0}^1\frac{1}{2}h_v(...)$. Door alle paren}} \\ 
&\mbox{\comm{samen te nemen die enkel verschillen in \'e\'en $z$-waarde en (\ref{hvinequality}) toe te passen}}\\
&\le \frac{1}{2^v} \sum_{m=1}^{2^v}{}^*\left(2n-2v+2+\frac{1}{||ma_{1v-1}/2^{v-1}||}\right) \cdots \left(2n-2v+2+\frac{1}{||ma_{sv-1}/2^{v-1}||}\right) \\
&\mbox{\comm{$2n-2v+2+...$ wordt $2n-2(v-1)+...$, en de termen voor $m=2^{v-1}+1,2^{v-1}+3,...$}} \\
&\mbox{\comm{zijn gelijk aan de termen voor $m=1,3,...$. De sommatie valt dus uiteen in twee gelijke}} \\
&\mbox{\comm{van $m=1..2^{v-1}$}} \\
&=h_{v-1}
\end{aligned}
\end{equation}
Since $a_{11} = \cdots = a_{s1} = 1$, it follows that
\begin{equation*}
h_1 = \frac{1}{2}\sum_{m=1}^2{}^*\left(2n-2+\frac{1}{||m/2||}\right) \cdots \left(2n-2+\frac{1}{||m/2||}\right) = 2^{s-1}n^s,
\end{equation*}
and, consequently, \ref{eqn:vlev-1} gives us that
\begin{equation*}
h_n \le h_{n-1} \le \cdots \le h_1 \le 2^{s-1}n^s
\end{equation*}
We now estimate the quantities $H_v$. Obviously,
\begin{equation*}
H_1=(2^{n+1}-2)h_1=(2^n-1)2^sn^s<(2n)^s2^n
\end{equation*}
\comm{Bij $v=1$ valt de sommatie uit de definitie van $H_v$ weg.}
Since
\begin{equation*}
h_v=\frac{1}{2^v}\sum_{m=1}^{2^v}{}^*\left(2n-2v+\frac{1}{||ma_{1v}/2^v||}\right)\cdots\left(2n-2v+\frac{1}{||ma_{sv}/2^v||}\right)\end{equation*}
we get for $v\ge2$ that
\begin{align*}
H_v &\le \sum_{k=1}^{v-2} \sum_{m=1}^{2^k} {}^*\frac{1}{||ma_{1k}/2^k|| \cdots ||ma_{sk}/2^k||}+2^{v-1}h_{v-1}+(2^{n+1}-2^v)h_v \\
&\le \sum_{k=1}^{v-2} \sum_{m=1}^{2^k} {}^*\frac{1}{||ma_{1k}/2^k|| \cdots ||ma_{sk}/2^k||}+(2^{n+1}-2^{v-1})h_{v-1}=H_{v-1}
\end{align*}
\comm{De eerste lijn volgt uit het weglaten van $k=v-1$ uit de sommatie. De tweede lijn volgt dan uit het feit dat $h_v\le h_{v-1}$. NOTA: mijns inziens zou de gelijkheid in de eerste lijn enkel opgaan in het geval $v=n+1$. De tweede ongelijkheid komt wel voor uit de vorige resultaten.}

and, consequently
\begin{equation}
\label{eqn:3}
H_n \le H_{n-1} \le \cdots \le H_1 < (2n)^s2^n
\end{equation}
According to the definition of $a_j$ and $a_{jk}$,
\begin{equation*}
a_1 \equiv a_{1k},\dots,a_s \equiv a_{sk}\mbox{\hspace{12pt}} \pmod{2^k}
\end{equation*}
for $k=1,\dots,n$. But then it is obvious that
\begin{align*}
&\sum_{m=1}^{2^n-1}\frac{1}{||ma_{1}/2^n|| \cdots ||ma_{s}/2^n||} = \sum_{k=1}^n\sum_{m=1}^{2^k}{}^*\frac{1}{||ma_{1}/2^k|| \cdots ||ma_{s}/2^k||}\\
&\mbox{\comm{$\frac{1}{2^n},\frac{2}{2^n},...,\frac{2^{n-1}-1}{2^n} = \frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},...$}} \\
=&\sum_{k=1}^{n-1}\sum_{m=1}^{2^k}{}^*\frac{1}{||ma_{1k}/2^k|| \cdots ||ma_{sk}/2^k||}+\sum_{m=1}^{2^n}{}^*\frac{1}{||ma_{1n}/2^n|| \cdots ||ma_{sn}/2^n||}=H_n
\end{align*}
\comm{De eerste gelijkheid volgt uit het afsplitsen van de term voor $k=n$. De eerste term past dan rechtstreeks in de definitie van $H_n$, de tweede term komt overeen met $(2^{n+1}-2^n)h_n=2^nh_n=\sum_{m=1}^{2^n}{}^*\frac{1}{||ma_{1n}/2^n|| \cdots ||ma_{sn}/2^n||}$}
Hence by (\ref{eqn:3}),
\begin{equation}
\label{eqn:4}
\sum_{m=1}^{2^n-1}\frac{1}{||ma_{1}/2^n|| \cdots ||ma_{s}/2^n||} < (2n)^s2^n
\end{equation}
\comm{NOTA: voor $m=2^n$ wordt de noemer gelijk aan 0!}
We determine $b$ and $b_2,\dots,b_s$ with the help of the congruences
\begin{equation*}
a_1b\equiv 1, a_2b \equiv b_2 , \dots, a_sb \equiv b_s  \pmod{2^n}
\end{equation*}
\comm{De vergelijkingen zijn altijd oplosbaar want $a_i$ is oneven en dus inverteerbaar in de groep mod $2^n$. NOTA: Dits is geen stelsel, nadat $b$ bepaald is uit de eerste vergelijking kunnen alle $b_i$'s afzonderlijk bepaald worden. }
Then from (\ref{eqn:4}) it follows that
\comm{Voor de functie $f(x)=||x/2^n||$ geldt dat $x = x\pmod{2^n}$. In de groep mod $2^n$ is $b=a_1^{-1}$ een eenduidig bepaald oneven geheel getal. Vermenigvuldiging van de gehele getallen modulo $2^n$ met $b$ levert een permutatie op van de gehele getallen modulo $2^n$. In de sommatie \ref{eqn:4} kan $m$ overal vervangen worden door $bm$, enkel de volgorde van de sommatie wordt dan omgewisseld.}
\begin{align*}
&\sum_{m=1}^{2^n-2}\frac{1}{||m/2^n||\cdot||b_2m/2^n|| \cdots ||b_sm/2^n||} < (2n)^s2^n,\\
&\mbox{\comm{NOTA: Schrijffout? Volgens mij zou de sommatie moeten lopen tot $2^n-1$.}} \\
&\sum_{m=1}^{2^n-1}\frac{1}{m||b_2m/2^n|| \cdots ||b_sm/2^n||} < (2n)^s,
\end{align*}
\comm{Hier wordt gebruikt dat $m\ge2^n||m/2^n||$. In het geval $m\le2^{n-1}$ geldt $||m/2^n||=m/2^n$, in het geval $m>2^{n-1}$ geldt dat $m=2^{n}-b$ met $b<2^{n-1}<m$. Er geldt dan dat $||m/2^n||=||b/2^n||=b/2^n<m/2^n$.}
and consequently, for $m=1,2,\dots,2^{n-1}$
\begin{equation*}
m\left\|\frac{b_2m}{2^n}\right\| \cdots \left\|\frac{b_sm}{2^n}\right\|>\frac{1}{(2n)^s}.
\end{equation*}
\comm{Als de ongelijkheid geldt voor de som, geldt ze ook voor de termen apart aangezien alle termen positief zijn.}
Since $p=2^n$, we have that $2n<3\ln{p}$ and
\comm{$3\ln{p}=3n\ln{2}=2,0974n$.}
\begin{equation}
\label{eqn:5}
m\left\|\frac{b_2m}{p}\right\| \cdots \left\|\frac{b_sm}{p}\right\|>\frac{1}{3^s\ln^s{p}}, \mbox{\hspace{12pt}}1\le m\le\frac{1}{2}p.
\end{equation}
As shown in \cite{korobov1967} (Corollary 2 of Theorem 7), the estimate (\ref{eqn:5}) implies that if $p$ is prime, then $1,b_2,\dots,b_s$ and hence also $a_1,\dots,a_s$, are optimal coefficients modulo $p$. This optimality condition is not hard to extend also to the case when $p$ is a power of a prime number. But then the theorem obviously follows from (\ref{eqn:5}).
\end{proof}

\section*{Derivation of (\ref{eqn:5})}
\emph{From \cite{korobov1967}}

\bibliographystyle{plain}
\bibliography{../library}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: